package com.lry.basic.algorithm.common;

/**
 * @author:刘仁有
 * @desc: 搜索旋转后的排序数组的某个元素，假设按照升序排序的数组在预先未知的某个点上进行了旋转。
 * @email:953506233@qq.com
 * @data:2019/9/6
 */
public class SearchRotateSortArr {
    public static void main(String[] args) {
//        System.out.println(search(new int[]{4,5,6,7,8,1,2,3}, 7));
//        int[] res = searchRange(new int[]{5,8,8,8,8,9}, 8);
//        System.out.println(res[0]+" "+res[1]);
//        System.out.println(searchLeft(new int[]{1, 1, 1, 1, 2}, 2));
//        System.out.println(searchRight(new int[]{1,2,2,2,2}, 2));
        System.out.println(search1(new int[]{3,1,1},3));

    }
    //在排序数组中查找元素的第一个位置和最后一个位置
    public static int[] searchRange(int[] nums, int target) {
        int[] result = new int[]{-1,-1};
        if(null==nums||nums.length==0)return result;
        result[0]=searchLeft(nums,target);
        result[1]=searchRight(nums,target);
        return result;
    }
    // 1 2 2 2 3 寻找2的左侧边界下标1
    public static int searchLeft(int[] nums,int target){
        if(null==nums||nums.length==0)return -1;
        int low=0,high=nums.length-1;
        while(low<=high){
            int mid = (low+high)>>>1;
            if(nums[mid]==target){
                if(mid==0||nums[mid-1]!=target){
                    return mid;
                }else if(nums[mid-1]==target) {
                    high = mid-1;
                }
            }else if(target>nums[mid]){
                low = mid+1;
            }else if(target<nums[mid]){
                high = mid-1;
            }
        }
        return -1;
    }

    public static int searchRight(int[] nums,int target){
        if(null==nums||nums.length==0)return -1;
        int low=0,high=nums.length-1;
        while(low<=high){
            int mid = (low+high)>>>1;
            if(nums[mid]==target){
                if(mid==nums.length-1||nums[mid+1]!=target){
                    return mid;
                }else if(nums[mid+1]==target) {
                    low = mid+1;
                }
            }else if(target>nums[mid]){
                low = mid+1;
            }else if(target<nums[mid]){
                high = mid-1;
            }
        }
        return -1;
    }

    public static int search(int[] nums){
        int low = 0;
        int high = nums.length-1;
        while(low<high){
            int mid = (low+high)>>>1;
            if(nums[mid]>nums[high]){
                low = mid+1;
            }else{
                high = mid;
            }
        }
        return nums[low];
    }
    //2,5,6,7, 0,1,2
    public static boolean search1(int[] nums,int target){
        if(null==nums||nums.length==0){
            return false;
        }

        int low = 0;
        int high = nums.length-1;
        while(low<=high){
            int mid = low+(high-low)/2;

            int left = 1;
            for(int i=low;i<high;i++){
                if(nums[i+1]>=nums[i]){
                    left++;
                }else{
                    break;
                }
            }

            //左边的有序多
            if(left*2>=high-low+1){
                if(target==nums[mid]){
                    return true;
                }else if(target<nums[mid]&&target>=nums[low]){
                    high = mid-1;
                }else{
                    low = mid+1;
                }
            }else{
                if(target==nums[mid]){
                    return true;
                }else if(target>nums[mid]&&target<=nums[high]){
                    low = mid+1;
                }else{
                    high = mid-1;
                }
            }
        }
        return false;
    }

    public static int search(int[] nums, int target) {
        if(null==nums||nums.length==0)
            return -1;
        int low = 0;
        int high = nums.length-1;
        while(low<=high) {
           int mid = (low + high) >>> 1;
           //左边有序的多 2 3 4 5 6 7 1
            if(nums[mid]>=nums[high]){
                if (target == nums[mid]) {
                    return mid;
                } else if (target >= nums[low] && target < nums[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }else{  //右边有序的多 7 1 2 3 4 5 6
                if (target == nums[mid]) {
                    return mid;
                } else if (target <= nums[high] && target > nums[mid]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }
}
